package cn.mayday.algorithms.year2021.month1.深度优先遍历;

/**
 * 剑指 Offer 36. 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * <p>
 * 难度中等
 *
 * @author: mayday
 * @date: 2021/5/12 23:39
 * @version: 1.0
 */
public class Offer036TreeToDoublyList {


    public static void main(String[] args) {

    }
//    解题思路：
//    本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。
//    将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
//
//    1、排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
//    2、双向链表： 在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur ，不仅应构建 pre.right = cur ，也应构建 cur.left = pre 。
//    3、循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。

    Node preTempNode; // 定义前继节点
    Node headResultNode; // 定义返回节点的头结点,永远不变

    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return null;
        }
        // 步骤一：中序二叉树遍历，步骤二:并在DFS遍历中完成节点指向关系
        dfs(root);

        // 步骤三： 完成头结点和尾结点的串联(//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的)
        preTempNode.right = headResultNode;
        headResultNode.left = preTempNode;

        return headResultNode;
    }

    /**
     * @param cur 当前节点
     */
    public void dfs(Node cur) {
        if (cur == null) {
            return;
        }
        // 注意DFS的中序遍历模板方法就是这样
        dfs(cur.left);

        // DFS步骤二：process 当前节点和前继节点互相指向
        if (preTempNode == null) {
            headResultNode = cur; // 前继节点为空，那当前节点就是头结点
        } else { // 如果前继节点不为空，当前节点指向前继节点的右边
            preTempNode.right = cur;
        }
        //pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
        cur.left = preTempNode; // 前继节点指向当前节点的左边

        preTempNode = cur;  //pre更新为当前节点（继续下一次）

        dfs(cur.right);
    }

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}
